package com.lzy.algorithm;

public class 环路检测 {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(7);
        ListNode l2 = new ListNode(6);
        ListNode l3 = new ListNode(0);
        ListNode l4 = new ListNode(-1);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l2;

        ListNode node = detectCycle(l1);
        System.out.println(node.val);
    }

    public static ListNode detectCycle(ListNode node) {
        ListNode fast = node;
        ListNode low = node;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;
            low = low.next;

            if (fast == low) {
                break;
            }
        }

        if (fast == null || low == null) {
            return null;
        }

        fast = node;
        while(true){
            fast = fast.next;
            low = low.next;
            if(fast == low){
                return fast;
            }
        }
    }
}
